package com.xyj.rxhui.week00.review;

import com.xyj.common.ListNode;

/**删除倒数第n个节点  、
 * 思路：先找到这个节点  然后将这个节点的前个节点指到这个节点的后面
 * @author GuXiaoYao
 * @version 1.0.0
 * @since 2021/12/6
 */
public class T4 {



    public ListNode removeNthFromEnd(ListNode head, int n) {

       if (head==null ){
           return null;
       }
       // 构建一个虚拟节点
        ListNode dummyNode=new ListNode(-1);
        dummyNode.next=head;

        // 找到我们想要删除的节点的前一个节点
        ListNode theDeletedOnePre = this.findTheLastOne(dummyNode, n+1);
        // 删除该节点
        theDeletedOnePre.next=theDeletedOnePre.next.next;
        return dummyNode.next;

    }

    private ListNode findTheLastOne(ListNode head, int n) {

        ListNode fast=head;
        // 快指针先走n步
        for (int i = 0; i < n; i++) {
            fast=fast.next;
        }
        ListNode slow=head;
        // 快指针走到头  慢指针走到倒数第k个
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;


    }


}
